"""
思路:
i 位置的水量 = min(leftMax[i], rightMax[i]) - height[i]
leftMax, rightMax 分别为，左边的最大高度，和右边的最大高度
"""

from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        left_max = []
        right_max = [0] * len(height)

        tmp = height[0]
        for v in height:
            tmp = max(tmp, v)
            left_max.append(tmp)

        tmp = height[-1]
        for i in range(len(height) - 1, -1, -1):
            tmp = max(tmp, height[i])
            right_max[i] = tmp

        res = []
        for i in range(len(height)):
            res.append(min(left_max[i], right_max[i]) - height[i])
        return sum(res)


if __name__ == "__main__":
    res = Solution().trap([3, 2, 3])
    print(res)
